# 二叉树 路径总和
from collections import defaultdict

class TreeNode:
    def __init__(self, val=0, left=None, right=None):

        self.val = val
        self.left = left
        self.right = right


class Solution:
    def pathSum(self, root, targetSum) -> int:
        ans = 0
        cnt = defaultdict(int)
        cnt[0] = 1

        def  dfs(node, s):
            # 找到终止条件
            if not node:
                return
            
            nonlocal ans # 声明 ans 是外层作用域的变量，可以在内层函数修改
            s += node.val # 将当前节点的值累加到 s 中，表示从根节点到当前节点的路径和
            ans += cnt[s - targetSum] # 快速查询这样的前缀和出现了多少次
            cnt[s] += 1 # 将当前的前缀和记录下来，供后续节点使用
            dfs(node.left, s)
            dfs(node.right, s)
            cnt[s] -= 1 # 撤销当前前缀和的计数

        dfs(root, 0)

        return ans



